The principle of the “TRIE” memory was proposed by R. de la Briandais and E. Fredkin toward the end of the 1950s (see E. Fredkin et al.: “Trie Memory”, Communications of the ACM, Vol. 3, No. 9, September 1960, pages 490-499). It involves dividing bit strings to be recognized into successive sections of fixed length (of K bits) and incorporating them into a two-dimensional table T. Each line of the table forms a register of 2K individual cells. A register (R) is allocated to each section of the string and a cell in the register is associated with the value (V), lying between 0 and 2K−1 of that section. The content (C=T[R,V]) of the cell thus determined represents either the register allocated to the next section (or pointer), or an end-of-analysis reference (or “status”) if the analysis of the string must terminate on that section.
The register allocated to the first section of the string, that is also the entry point of the table, is called a portal. The data to be analyzed in the form of bit strings, i.e. to be compared with the content of the TRIE memory, will also be called routes hereinafter. The succession of stringed cells associated with a route will be called a path in the table. Each register of the table will be of the order i≧0 if it is allocated to the (i+1)th section of one or more stored routes. The portal register is therefore of the order 0. The TRIE memory associates with each of its registers of the order i≧0 a unique sequence of iK bits corresponding to the first iK bits of each route whose path in the table passes through a cell of the register in question.
The following example shows a representation of the storage of the data in a TRIE memory in the particular case in which K=4. The value of each section is represented by a digit in hexadecimal numbering (0,1, . . . ,E,F), and the registers each contain 24=16 cells.
Assume that the routes that begin with the patterns 45A4, 45AB, 67AB, 788A and 788BD, to which the statuses S0, S1, S2, S3 and S0 are allocated respectively (one and the same status may be shared by several routes) are to be recognized. By setting out the register R by position in the line, the value V of the sections by position in the column, and by taking as the portal the register R0=0, the TRIE memory table may be presented as shown in FIG. 1, where the underlined data are statuses. The patterns 45A4, 45AB, 67AB, 788A and 788BD are respectively represented in the table of FIG. 1 by the paths:
T[0, 4] → T[1, 5] → T[2, A] → T[3, 4];T[0, 4] → T[1, 5] → T[2, A] → T[3, B];T[0, 6] → T[4, 7] → T[5, A] → T[6, B];T[0, 7] → T[7, 8] → T[8, 8] → T[9, A];T[0, 7] → T[7, 8] → T[8, 8] → T[9, B] → T[10, D].It can be seen in this example that all the patterns beginning with a common part of iK bits are represented by a common beginning of a path in the memory, leading to the register of order i with which the sequence formed by these iK bits is associated.
If consideration is given to a route to be analyzed, divided into a series of binary sections of values Vi where 0≦i≦N and {Ri} the sequence of registers associated with the values Vi, R0 again designating the portal register, the analysis algorithm applied may be that shown in FIG. 2.
On the initialization 1 of this algorithm, the analysis rank i is set to 0 and the portal register R0 is selected as the register r. In each iteration of rank i, the content C of the cell T[r,Vi] designated by the (i+1)th section Vi of the route in the selected register of the order i is read in step 2. If this cell contains an analysis continuation pointer, which, in the test 3, the value 1 of a bit FP(C) stored in the cell indicates, the register of order i+1 designated by this pointer Ptr(C) is selected as the register r for the next iteration in step 4, and the rank i is incremented. When the test 3 reveals a cell that does not contain a pointer (FP(C)=0), the status Ref(C) read in the cell concerned is returned in step 5 as the result of the consultation of the table.
This algorithm allows routes comprising any number of sections to be analyzed. One and the same table may be used for several types of analyses by managing the data from different portals. In addition, it makes it possible to control the data analysis time: the analysis of a number N of sections of K bits will last no more than N times the duration of an iteration.
The algorithm of FIG. 2 may be applied very rapidly by a hardware component managing the access points to the memory table. In particular, it allows the production of high performance routers for packet-switched telecommunications networks. The packet header is analyzed on the fly by the component, and the status associated with a route designates for example an output port of the router to which the packets carrying a destination address complying with this route must be forwarded.
Such a router may be a multi-protocol router. For this, different portions of the header are analyzed based on different portals. For example, a first analysis of one or more fields of the header designating the protocol used and/or the version of this protocol may be analyzed based on a first portal. This first analysis supplies a reference which, although corresponding to a logical end of analysis, may be materialized in the TRIE memory by an analysis continuation pointer designating another portal register to be used to analyze the rest of the header. The reference in question may also trigger timers or skips of a determined number of bits in the analyzed header in order to be able to choose which portion of the header must be analyzed next. In practice, a certain number of analyses are usually carried out successively, to trigger the operations required by the protocols supported according to the content of the headers. One of these analyses will relate to the destination address to accomplish the actual routing function.
The fact that it is possible to string together several individual analyses with programmable skips between them provides the process with great flexibility, particularly for processing protocols encapsulated according to several layers of the OSI model. Analysis on the fly of the sections of the header as and when they arrive furthermore provides great speed.
Another advantage of TRIE tables is that they allow routing requirements to be taken into account on the basis of the longest path recorded corresponding to a prefix of the route to be recognized, a requirement that is encountered in particular in the context of IP routing (see EP-A-0 989 502).
EP-A-1 030 493 discloses a TRIE memory whose content includes, in addition to the actual references associated with the packet headers, a program consisting in stringing together individual analyses to be carried out according to the various configurations taken into account by the memory. These strings are fully programmable. The user can arbitrarily, and at each step of the process, define which portion of the header must be examined and based on which register of the TRIE memory, thereby providing great processing flexibility.
A TRIE memory may also be described as a tree with nodes distributed at several successive stages corresponding to the previously mentioned orders of analysis i. Each node of a stage i represents a decision to be taken during the analysis of the (i+1)th section of a route. The root-node of the tree corresponds to the portal register, the leaf-nodes correspond to the statuses and the intermediate nodes correspond to the registers designated by the analysis continuation pointers. The tree representation makes it easy to view the paths. The tree of FIG. 3 thus shows the paths recorded in the table of FIG. 1, the root and the intermediate nodes being represented by circles (registers) and the leaves by rectangles (statuses).
The tree representation makes it possible to design compression methods aimed at reducing the memory size required to use a TRIE table. This reduction is particularly useful for rapid implementations of large-sized tables by means of static RAM (SRAM) circuits. A hardware realization in table form in which each register comprises 2K cells is specifically not very effective in terms of memory occupancy since such a table comprises many empty cells, as shown in FIG. 1. When the tree is occupied by a large number of random data items, the nodes close to the root have a number of valid descendants close to the number of descendants possible (2K). On the other hand, when further from the root, the average number of valid descendants of a given node diminishes considerably and tends toward 1 (or 2 if a default status is included). In this case, there is only 10% and 15% useful cells in the memory.
The article “An Experimental Study of Compression Methods for Functional Tries” by J-P. Livonen, et al., submitted to the WAAPL′99 conference (1999) reviews several known compression methods that can be combined:                path compression consists in aggregating, on a node Y of a stage i, the nonempty nodes of the stages i+1 to i+j−1 (j≧2) that are the descendants of this node Y when each of these nodes of the stages i to i+j−1 has a single nonempty descendant (register or status). See also U.S. Pat. Nos. 6,014,659 and 6,505,206. The length of the section to be analyzed in relation with the compressed node Y is multiplied by j;        level compression consists in aggregating, on a node Z of a stage i, the nonempty nodes of the stages i+1 to i+j−1 (j≧2) that are descendants of this node Z when each of these nodes of the stages i+1 to i+j−1 has itself at least one nonempty descendant (register or status). The length of the section to be analyzed in relation with the compressed node Z is multiplied by j;        width compression, or pointer compression, consists in eliminating the empty descendants of a given node. See also U.S. Pat. No. 5,781,772, EP-A-0 458 698 or WO 00/75804. There is no point in reserving a register of 2K cells to analyze a section having only L<2K valid values in paths recorded in the TRIE memory: it is possible to be content with a compressed zone of L cells, associated with cartographic data indicating the valid values of the section. These cartographic data typically take the form of a bitmap vector of 2K bits set at 1 in L positions corresponding to the L valid values of the section and at 0 in the other 2K-L positions.        
In the path and level compression methods, modifying during the analysis the length of the divided sections in the data to be analyzed lends itself poorly to a fast implementation in a specific hardware component. Essentially it makes it possible to reduce the memory size required for a software implementation that is by nature less rapid.
The width compression method does not suffer from this limitation. However, it requires the actual analysis of a section to be preceded by the analysis of the associated bitmap to validate the value of the section and locate the corresponding cell. This method may be implemented in a rapid hardware model, but a limitation to this rapidity is that its complexity increases greatly with the width K of the section. Specifically, the function used to obtain the address of the successor of a given node requires resources (node size) of a complexity proportional to 2K.
Furthermore, a TRIE table lends itself to parallel processing in pipeline mode, as evoked in the article “Putting Routing Tables in Silicon”, by T-B. Pei et al., IEEE Network Magazine, January 1992, pages 42-50. If the maximum number of stages of the tree is equal to M, that is to say if the data strings to be analyzed can go up to M×K bits, the available memory space can be divided into N memory planes, where N≦M. Each memory plane Pj of level j (0≦j<N) is reserved for the nodes of one or more consecutive stages of the tree. N operators function in parallel each with a respective buffer containing a data string to be analyzed. While one of the N operators carries out an analysis at the order or consecutive orders of the level j, by accessing the memory plane Pj, another operator may access the memory plane Pj−1 to carry out the analysis of a subsequent data string at the order or the consecutive orders of the level j−1. This pipeline processing by the N operators increases the maximum processing speed of the device.
An object of the present invention is to propose an effective method of compressing a TRIE memory, which facilitates the high speed processing of data strings to be analyzed and can be implemented by a hardware component of limited complexity.